#include <stdio.h>
#include <vector>

using namespace std;

const int MaxLog = 19; //该值取决于log(节点数)，19 > log(50万)

struct Node
{
    int value;
    int depth;
    Node *fa[MaxLog+1] = {0}; // 往上2^i层的父节点
    vector<Node *> child;
    Node()
    {
        value = -1;
        depth = 0;
    }
    Node(int v)
    {
        value = v;
        depth = 0;
    }
};

struct Tree
{
    vector<Node *> nodeSet;
    Tree(int nodeCount)
    {
        nodeSet = vector<Node *>(nodeCount);
        for (int i = 0; i < nodeCount; ++i)
        {
            nodeSet[i] = new Node(i);
        }
    }
    void AddEdge(int f, int t)
    {
        nodeSet[f]->child.push_back(nodeSet[t]);
    }
    //查询前要先调用一遍这个DFS做预处理，以生成depth和fa等数据
    void LCA_DFS(int cur, int father)
    {
        auto curNode = nodeSet[cur];
        curNode->depth = nodeSet[father]->depth + 1;
        curNode->fa[0] = nodeSet[father];
        for (int i = 1; i <= MaxLog; ++i)
        {
            if(curNode->fa[i - 1] == NULL)
                break;
            else //当前往上2^i层节点 = 当前往上2^(i-1)的父节点往上2^(i-1)层
                curNode->fa[i] = curNode->fa[i - 1]->fa[i - 1];
        }
        for(auto n : curNode->child)
        {
            if(n->value != father)
                LCA_DFS(n->value, cur);
        }
    }
    //查询a和b的公共祖先，时间复杂度O(logN)
    int LCA(int a, int b)
    {
        auto nodeA = nodeSet[a];
        auto nodeB = nodeSet[b];
        //先确保让a成为深度较深的那个
        if(nodeA->depth < nodeB->depth)
        {
            nodeA = nodeSet[b];
            nodeB = nodeSet[a];
        }
        //让二者来到同一深度
        for (int i = MaxLog; i >= 0; --i)
        {
            if(nodeA->fa[i] == NULL)
                continue;
            if(nodeA->fa[i]->depth >= nodeB->depth)
                nodeA = nodeA->fa[i];
        }
        if(nodeA == nodeB) //如果恰巧b就是a的最近父节点
            return nodeB->value;
        //当二者来到同一层，一同向上搜，直到来到公共祖先的下一层
        for (int i = MaxLog; i >= 0; --i)
        {
            if(nodeA->fa[i] == NULL)
                continue;
            if(nodeA->fa[i] != nodeB->fa[i])
            {
                nodeA = nodeA->fa[i];
                nodeB = nodeB->fa[i];
            }
        }
        return nodeA->fa[0]->value;//此时的父节点即为最近公共祖先
    }
};